package com.company.Sort;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}11:04
 */
public class MergetSort2 {
    public static void main(String[] args) {
        int arr[] = {8, 4, 5, 7, 1, 3, 6, 2};
    }

    //合并方法

    /**
     *
     * @param arr   需要排序的原始数组
     * @param left  左边有序序列的初始索引
     * @param right 右边有序序列的初始索引
     * @param mid   中间索引
     * @param temp  做中转的数组
     */
    public static void merge(int[] arr,int left,int right,int mid,int[] temp){
        int i = left;//做半边数组的起始索引
        int j = mid + 1;//右半边数组的起始索引
        int t = 0;//空数组的起始索引

        //（一）
        //先把左右两边的数组填充到temp数组
        //直到左右两边的有序序列，有一边处理完毕为止
        while (i <= mid&& j <= right){
            if (arr[i] <= arr[j]){
                temp[t] = arr[i];
                i++;
                t++;
            }else {
                temp[t] = arr[j];
                t++;
                j++;
            }
        }


        //（二）
        //把有剩余数据的一边的数据依次全部填充到temp
        while(i < mid){//左边剩余
            temp[t] = arr[i];
            i++;
            t++;
        }

        while(j < right){//右边剩余
            temp[t] = arr[j];
            j++;
            t++;
        }

        //（三）
        //将temp数组的元素拷贝到arr
        //并不是每次都是拷贝所有的
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right){
            arr[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }
    }
}
